import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;


public class SDRparser 
{
	UnaryRuleTranslator u; 
	static int numberOfTypeRaisesAllowed = 1;
	static CategoryAnalyst analyst = new CategoryAnalyst();
	public SDRparser(UnaryRuleTranslator u)
	{
		this.u = u;
	}
	
	/*
	 * Takes an arraylist of "Sign" objects in the order that they appear
	 * in the sentence.  Outputs a completed chart.
	 */
	
	public Chart parse(ArrayList<Sign> input)
	{
		
		//initialize the chart
		Chart theChart = new Chart(input.size()+1);
		for(int a = 0; a < input.size(); a++)
		{
			theChart.addToChart(input.get(a), a, a+1);
		}
		
		
		//cross the chart vertically, backwards
		for(int a = input.size()-1; a >= 0; a--)
		{
			//cross the chart horizontally, rightwards
			for(int b = a; b <= input.size(); b++)
			{
				//try type raising
				for(int c = a+1; c < b; c++)
				{
					HashSet<Sign> s1 = theChart.getSigns(a, c); // all the potential left sides
					HashSet<Sign> s2 = theChart.getSigns(c, b); // all the potential right sides
					
					Iterator i = s1.iterator();
					ArrayList<Sign> tempAddingThing1 = new ArrayList<Sign>();
					ArrayList<Sign> tempAddingThing2 = new ArrayList<Sign>();
					//iterate through both lists...
					while(i.hasNext())
					{
						Sign iSign = (Sign) i.next();
						Iterator j = s2.iterator();
						while(j.hasNext())
						{
							
							Sign jSign = (Sign) j.next();
							
							Sign resultTypeRaiseRight = typeRaiseRight(iSign,jSign);
							if(resultTypeRaiseRight != null)
							{
								resultTypeRaiseRight.incComplexity();
								for(Sign spotlight : iSign.getHeads())
								{
									Dependency p = new Dependency(spotlight,spotlight,resultTypeRaiseRight,0);
									resultTypeRaiseRight.addToParglist(p);
									tempAddingThing1.add(resultTypeRaiseRight);
									//theChart.addToChart(resultTypeRaiseRight, a, c);
								}
							}
							
							Sign resultTypeRaiseLeft = typeRaiseLeft(iSign,jSign);
							if(resultTypeRaiseLeft != null)
							{
								resultTypeRaiseLeft.incComplexity();
								for(Sign spotlight : jSign.getHeads())
								{
									Dependency p = new Dependency(spotlight,spotlight,resultTypeRaiseLeft,0);
									resultTypeRaiseLeft.addToParglist(p);
									tempAddingThing2.add(resultTypeRaiseLeft);
									//theChart.addToChart(resultTypeRaiseLeft, a, c);
								}
							}
						}
					}
					Iterator k = tempAddingThing1.iterator();
					while(k.hasNext())
					{
						Sign spotlight = (Sign) k.next();
						theChart.addToChart(spotlight,a,c);
					}
					Iterator k2 = tempAddingThing2.iterator();
					while(k2.hasNext())
					{
						Sign spotlight = (Sign) k2.next();
						theChart.addToChart(spotlight,c,b);
					}
				}//end type raising
				
				
				
			
				//for all the places we can break this string in half...
				for(int c = a+1; c < b; c++)
				{
					HashSet<Sign> s1 = theChart.getSigns(a, c); // all the potential left sides
					HashSet<Sign> s2 = theChart.getSigns(c, b); // all the potential right sides
					Iterator i = s1.iterator();
					
					//iterate through both lists...
					while(i.hasNext())
					{
						Sign iSign = (Sign) i.next();
						Iterator j = s2.iterator();
						while(j.hasNext())
						{
							Sign jSign = (Sign) j.next();
							
							
							
							//forward application
							Sign resultFapply = fapply(iSign,jSign);
							if(resultFapply != null)
							{
								for(Sign spotlight : iSign.getHeads())
								{
									for(Sign spotlight2 : jSign.getHeads())
									{
										Dependency p = new Dependency(spotlight, spotlight2, resultFapply, iSign.getNumOfArgs());
										resultFapply.addToParglist(p);
										
										DennisDependency d;
										if(resultFapply.isHeadOnLeft())
										{
											d = new DennisDependency(spotlight.getStringIndex(), spotlight2.getStringIndex());
										}
										else
										{
											d = new DennisDependency(spotlight2.getStringIndex(), spotlight.getStringIndex());
										}
										resultFapply.addToDennisDependencies(d);
										theChart.addToChart(resultFapply, a, b);
									}
								}
							}
							
							//backward application
							Sign resultBapply = bapply(iSign,jSign);
							if(resultBapply != null)
							{
								for(Sign spotlight : iSign.getHeads())
								{
									for(Sign spotlight2 : jSign.getHeads())
									{
										Dependency p = new Dependency(spotlight2, spotlight, resultBapply, jSign.getNumOfArgs());
										resultBapply.addToParglist(p);
										
										DennisDependency d;
										if(resultBapply.isHeadOnLeft())
										{
											d = new DennisDependency(spotlight2.getStringIndex(), spotlight.getStringIndex());
										}
										else
										{
											d = new DennisDependency(spotlight.getStringIndex(), spotlight2.getStringIndex());
										}
										resultBapply.addToDennisDependencies(d);
										
										theChart.addToChart(resultBapply, a, b);
									}
								}
							}
							Sign resultFcomp = fcomp(iSign,jSign);
							if(resultFcomp != null)
							{
								for(Sign spotlight : iSign.getHeads())
								{
									for(Sign spotlight2 : jSign.getHeads())
									{
										Dependency p = new Dependency(spotlight, spotlight2, resultFcomp, iSign.getNumOfArgs());
										resultFcomp.addToParglist(p);
										theChart.addToChart(resultFcomp, a, b);
									}
								}
							}
							
						//	Sign resultBcomp = bcomp(iSign,jSign);
						
							
						/*	if(resultBcomp != null)
							{
								for(Sign spotlight : iSign.getHeads())
								{
									for(Sign spotlight2 : jSign.getHeads())
									{
										Dependency p = new Dependency(spotlight, spotlight2, resultBcomp, iSign.getNumOfArgs());
										resultBcomp.addToParglist(p);
										theChart.addToChart(resultBcomp, a, b);
									}
								}
							}
							
							//function composition...
							*/
						}
					}
				}
				//end binary
				
//try unary rules
				
				HashSet<Sign> s = theChart.getSigns(a,b);
				ArrayList<Sign> r = new ArrayList<Sign>();
				for(Sign spotlight : s)
				{
					ArrayList<Sign> result = u.translate(spotlight);
					r.addAll(result);
				}
				for(Sign spotlight : r)
				{
					spotlight.incComplexity();
					theChart.addToChart(spotlight, a, b);
				}
			}
		}
		return theChart;
	}
	
	
	/*Forward application*/
	private Sign fapply(Sign left, Sign right)
	{
		//safety step -- if either are null then we can't do this application
		if(left == null || right == null)
			return null;
		
		SuperDuperTag leftSupertag = new SuperDuperTag(left.getSuperDuperTag());
		
		//make sure the slash is right.
		//TODO make this handle different slash modalities
		if(!(leftSupertag.getRightmostSlash().equals("/") || leftSupertag.getRightmostSlash().equals("/*")))
			return null;
		
		SuperDuperTag rightSupertag = new SuperDuperTag(right.getSuperDuperTag());
		
		/*
		 * String s is the topmost arg of leftSupertag.  For example,
		 * if leftSupertag is (S\NP)/NP, then s is NP.
		 */
		SuperDuperTag arg = leftSupertag.getRightmostArg();
		if(arg == null)
			return null;
		
		/*
		 * If the top arg matches the supertag on the right, then apply.
		 */
		//System.out.println("Does " + arg.toString() + " equal " + right.getSuperDuperTag().toString() + "?");
		if(arg.equals(right.getSuperDuperTag()))
		{
			Sign result;
			result = new Sign(leftSupertag, left, right);
			result.setThingsIHaveEaten(left.getThingsIHaveEaten());
			result.eatElement(right);
			int index = result.getLeftmostIndex();
			HashSet<Sign> signs = (HashSet) result.digForCoindexedElements(result, leftSupertag.getLeftmostIndex());
			if(signs.isEmpty())
			{
				result.addHead(left.getHead());
				result.setHeadOnLeft();
			}
			else
			{
				for(Sign x : signs)
				{
					result.addHead(x);
				}
			}
			result.setCreator("Forward Application");
			return result;
		}
		else
		{
		//	System.out.println("no.");
		}
		
	
		return null;
	}
	
	private Sign bapply(Sign left, Sign right)
	{
		//safety step -- if either are null then we can't do this application
		if(left == null || right == null)
			return null;
		
		SuperDuperTag rightSupertag = new SuperDuperTag(right.getSuperDuperTag());
		
		//make sure the slash is right.
		//TODO make this handle different slash modalities
		if(!(rightSupertag.getRightmostSlash().equals("\\") || rightSupertag.getRightmostSlash().equals("\\*")))
			return null;
		SuperDuperTag leftSupertag = new SuperDuperTag(left.getSuperDuperTag());
		String tagString = leftSupertag.toStringForComp();
		/*sfor(int a = 0; a < leftSupertag.getArgs().size();a++)
		{
			tagString+= leftSupertag.getSlashes().get(a);
			tagString+= leftSupertag.getArgs().get(a);
		}*/
		
		
		/*
		 * String s is the topmost arg of leftSupertag.  For example,
		 * if leftSupertag is (S\NP)/NP, then s is NP.
		 */

		String argString = rightSupertag.getArgs().get(0).toStringForComp();
	
		/*
		 * If the top arg matches the supertag on the right, then apply.
		 */
			if(argString.equals(tagString))
			{
				Sign result;
				result = new Sign(rightSupertag, left, right);
				result.setThingsIHaveEaten(right.getThingsIHaveEaten());
				result.eatElement(left);
				int index = result.getLeftmostIndex();
				HashSet<Sign> signs = (HashSet) result.digForCoindexedElements(result, rightSupertag.getLeftmostIndex());
				if(signs.isEmpty())
				{
					result.addHead(right.getHead());
					result.setHeadOnLeft();
				}
				else
				{
					for(Sign x : signs)
					{
						//System.out.println("adding a head: " + x.getStringIndex());
						result.addHead(x.getHead());
					}
				}
				result.setCreator("Backward Application");
				return result;
			}
		
		return null;
	}
	
	private Sign fcomp(Sign left, Sign right)
	{
		if(left == null || right == null)
			return null;
		
		if(left.getNumOfArgs() < 1 || right.getNumOfArgs() < 1)
			return null;
		
		SuperDuperTag leftSupertag = new SuperDuperTag(left.getSuperDuperTag());
		if(!leftSupertag.getRightmostSlash().equals("/"))
		{
			return null;
		}
		
		
		SuperDuperTag arg = leftSupertag.getRightmostArg();
		
		String argString = arg.toStringForComp();
		
		SuperDuperTag rightSupertag = new SuperDuperTag(right.getSuperDuperTag());
		String baseOfRightSupertag = rightSupertag.getBaseMinusSemantics();
		int z;
		for(z = 0; z < right.getSuperDuperTag().getNumOfArgs(); z++)
		{
			if(argString.equals(baseOfRightSupertag) && right.getSuperDuperTag().getSlashes().get(z).equals("/"))
			{
				Sign result = new Sign(leftSupertag, left, right);

				result.eatElement(right);
				int index = left.getLeftmostIndex();
				
				result.addHead(right.getHead());
				result.addHead(left.getHead());

				ArrayList<SuperDuperTag> temp1 = new ArrayList<SuperDuperTag>();
				for(int z1 = z; z1 < right.getSuperDuperTag().getArgs().size(); z1++)
				{
					temp1.add(right.getSuperDuperTag().getArgs().get(z1));
				}
				ArrayList<String> temp2 = new ArrayList<String>();
				for(int z2 = z; z2 < right.getSuperDuperTag().getSlashes().size(); z2++)
				{
					temp2.add(right.getSuperDuperTag().getSlashes().get(z2));
				}

				result.addToArgs(temp1,temp2);
				result.setCreator("Forward Composition");
				return result;
			}
			
			baseOfRightSupertag += right.getSuperDuperTag().getSlashes().get(z) + right.getSuperDuperTag().getArgs().get(z).toStringForComp();
		}
		return null;
	}
	
	private Sign bcomp(Sign left, Sign right)
	{
		if(left == null || right == null)
			return null;
		
		if(left.getNumOfArgs() < 1 || right.getNumOfArgs() < 1)
			return null;
		
		SuperDuperTag rightSupertag = new SuperDuperTag(right.getSuperDuperTag());
		if(!rightSupertag.getRightmostSlash().equals("\\"))
		{
			return null;
		}
		
		SuperDuperTag arg = rightSupertag.getRightmostArg();
		String argString = arg.toStringForComp();
		
		SuperDuperTag leftSupertag = new SuperDuperTag(left.getSuperDuperTag());
		String baseOfLeftSupertag = leftSupertag.getBaseMinusSemantics();
		
		int z;
		for(z = 0; z < left.getSuperDuperTag().getNumOfArgs(); z++)
		{
			if(argString.equals(baseOfLeftSupertag) && left.getSuperDuperTag().getSlashes().get(z).equals("\\"))
			{
				Sign result = new Sign(rightSupertag, left, right);

				result.eatElement(left);
				int index = right.getLeftmostIndex();
				HashSet<Sign> signs = (HashSet) result.digForCoindexedElements(result, right.getLeftmostIndex());
				if(signs.isEmpty())
				{
					//System.out.println("left");
					result.addHead(right.getHead());
				}
				else
				{
					//System.out.println("right");
					for(Sign x : signs)
					{
						//System.out.println("adding a head: " + x.getStringIndex());
						result.addHead(x);
					}
				}

				ArrayList<SuperDuperTag> temp1 = new ArrayList<SuperDuperTag>();
				for(int z1 = z; z1 < left.getSuperDuperTag().getArgs().size(); z1++)
				{
					temp1.add(left.getSuperDuperTag().getArgs().get(z1));
				}
				ArrayList<String> temp2 = new ArrayList<String>();
				for(int z2 = z; z2 < left.getSuperDuperTag().getSlashes().size(); z2++)
				{
					temp2.add(left.getSuperDuperTag().getSlashes().get(z2));
				}

				result.addToArgs(temp1,temp2);
				result.setCreator("Backward Composition");
				return result;
			}
			
			baseOfLeftSupertag += left.getSuperDuperTag().getSlashes().get(z) + left.getSuperDuperTag().getArgs().get(z).toStringForComp();
		}
		return null;
	}
	
	private Sign typeRaiseRight(Sign s, Sign toTheRight)
	{
		
		if(s.hasBeenTypeRaised())
			return null;
		if(s.getNormalFormVal() > numberOfTypeRaisesAllowed)
			return null;
		
		SuperDuperTag baseOfTagToRight = new SuperDuperTag(toTheRight.getSuperDuperTag().getBase());
		Sign result = new Sign(s);
		SuperDuperTag tag = result.getSuperDuperTag();
		SuperDuperTag formerBase = new SuperDuperTag(tag.getBase());
		ArrayList<SuperDuperTag> temp1 = new ArrayList<SuperDuperTag>();
		SuperDuperTag theArg = new SuperDuperTag("(" + baseOfTagToRight + "\\" + s.getSuperDuperTag().getBase() + ")");
		temp1.add(theArg);
		ArrayList<String> temp2 = new ArrayList<String>();
		temp2.add("/");
		tag.setBase(baseOfTagToRight.getBase());
		tag.addToArgsAtBegining(temp1, temp2);
		result.setCreator("R Type Raising");
		result.addHeads(s.getHeads());
		return result;
	}
	
	private Sign typeRaiseLeft(Sign toTheLeft,Sign s)
	{
		if(s.hasBeenTypeRaised())
			return null;
		if(s.getNormalFormVal() > numberOfTypeRaisesAllowed)
			return null;
		
		Sign result = new Sign(s);
		
		SuperDuperTag tag = result.getSuperDuperTag();
		tag.setBase(toTheLeft.getSuperDuperTag().getBase());
		ArrayList<SuperDuperTag> args = new ArrayList<SuperDuperTag>();
		ArrayList<String> slashes = new ArrayList<String>();

		SuperDuperTag theArg = new SuperDuperTag(toTheLeft.getSuperDuperTag().getBase() + "/" + s.getSuperDuperTag().getBase());
		args.add(theArg);
		slashes.add("\\");
		tag.addToArgs(args, slashes);
		result.setSuperDuperTag(tag);
		result.addHeads(s.getHeads());
		result.setCreator("L Type Raising");
		return result;
	}
}
